Rasterizing an image involves sampling input image data according to a transform specification to develop an output raster image. The input image can be obtained from many sources, such as, but not limited to, a scanner, facsimile transmission, video camera, CCD camera, digital camera, or satellite transmission. Such images are often digitized and stored in some form of permanent storage, such as a memory in a computer system. Other images may be generated synthetically by computer graphics generation programs, such as drawing or graphing programs.
A raster image is an image defined by y+1 scan lines, as shown in FIG. 1, each comprised of x+1 pixels. Displaying a raster image involves scanning through each scan line in the raster image in a direction X. When the scanning of a line is completed, the next line in direction Y is displayed in a similar manner.
A raster image is typically broken up into tiles 80 to simplify storage of the image in memory and to minimize disk accesses during processing of the image. A value for each pixel in a tile is stored sequentially according to the order of pixels in the scan line. Successive scan lines in the tile are also stored sequentially in memory. An image may be broken up into as few as one tile and as many as any arbitrary number of tiles supportable by the computer system.
Each pixel in a raster image may have either a binary representation (a 1 or 0) or a value taken from a range of discrete values, such as an 8-bit number (representing the range of integers from 0 to 255). Images whose pixels take on binary values are known as half tone images whereas images having any other representation are known as a continuous tone (contone) images.
A raster image may have one of many possible data representations. Commonly used representations include 1-plane, 3-plane, or 4-plane representations. A 1-plane image is typically a black and white image; a 3-plane image is typically a color image, often represented by red, green and blue (rgb) values; a 4-plane image is typically a color image, wherein pixels are often represented by cyan, magenta, yellow and black (cmyk) values. The term "plane" relates to how the data is grouped together. For example, for a 3-plane rgb image, all red information for all pixels is grouped together, separate from green and blue information. In a 1-plane rgb image all red, green and blue information for a pixel is grouped together. Many other representations are commonly used, and thus the invention is not limited to any specific data representation.
The transform specification indicates the orientation and size of the input image data in the space of the output raster image. A transform may be specified by a function in an interpretable language, such as PostScript. Given a specified transform and parameters of an output raster image, a 3.times.3 transform matrix may be defined, as shown in FIG. 2. The transform matrix provides an indication of the rotation and scaling of the input image data to be performed as well as its placement in the output raster image.
The transform matrix is used for, among other things, translating a coordinate (x.sub.i, y.sub.i) in the input space to a coordinate (x.sub.o, y.sub.o) in output space. For example, the coordinate (0, 0) is used to construct the three-dimensional vector [0, 0, 1] which is multiplied by the transform matrix to obtain the vector [e, f, l]. The integer part of (e, f) is the corresponding coordinate (x.sub.o, y.sub.o) in output space, and is the indication of the placement in the output raster image of the pixel in the input image having coordinate (0,0). The other values a, b, c and d of the transform matrix are affected by the desired rotation of the image. In general, x.sub.o =ax+cy+e and y.sub.o =bx+dy+f. Because x.sub.o and y.sub.o must be integers, they are truncated if necessary.
It should be understood that a transform matrix is not necessary to rasterization, and thus, to the present invention. Rasterization typically requires an indication of scaling of the input image in the x and y directions, an indication of any rotation and an offset in x and y between a pixel in the output image and the first pixel of the input image (e.g., (0, 0)). In some instances, the information given in a transform specification includes the input image size, the output image size and the position of the input image within the output image.
In general, rasterizing involves determining the appropriate mapping between pixels in the input image data and pixels in scan lines of the output raster image. In conventional rasterizing systems for use on digital computers, there is one generalized transform execution engine 30 (see FIG. 3) which receives as its input a transform specification 32 and input image data 34, to produce an output raster image 36.
Conventional rasterizers assume that each scan line in a raster image is different from any immediately previous scan line, which is true for all but orthogonal rotations. A well-known process using the transform specification allows a rasterizer to determine the mapping between the input image pixels and pixels in each scan line in the output raster image. The general transform execution engine of conventional rasterizing systems determines, using this process, the contents of every scan line even for various simple transforms. For orthogonal rotations and mirroring, computation time and resources are wasted by using this approach.